package 哈夫曼编码;

import java.lang.reflect.Array;
import java.util.*;

public class HuffmanCode{
    static List<Node> list = new ArrayList<>();
    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        List<Node> node = getNode(contentBytes);
        List<Node> nodes = huffmanTree(node);
        preSort(nodes.get(0));
    }
    // 通过list 创建huffman树
    public static List<Node> huffmanTree(List<Node> list){
        while (list.size()>1) {
            Collections.sort(list);

            Node left = list.get(0);
            Node right = list.get(1);

            Node node = new Node(null, left.wright + right.wright);
            node.left = left;
            node.right = right;
            list.remove(left);
            list.remove(right);
            list.add(node);
        }
        return list;
    }

    /**
     *
     * @param bytes 接受字节数组
     * @return 返回集合
     */
    private static List<Node> getNode(byte[] bytes){
        Map<Byte,Integer> map = new HashMap<>();
        for (byte b : bytes) {
            Integer integer = map.get(b);
            if(integer == null){
                map.put(b,1);
            }else {
                map.put(b, ++integer); // 即使替换,也是插入
            }
        }
        for(Map.Entry<Byte,Integer> entry: map.entrySet()){
            list.add(new Node(entry.getKey(),entry.getValue()));
        }
        return list;
    }

    //生成哈夫曼树对应的哈夫曼编码表
    // 将哈夫曼编码存放在Map<Byte,String> 中
    static Map<Byte,String> map = new HashMap<>();
    // 再生成哈夫曼编码的时候需要拼接路径,使用StringBuilder去拼接
    static StringBuilder sb = new StringBuilder();

    /**
     * 功能: 将传入的node节点的所有子节点得到,并将其保存在map集合中
     * @param node 头结点
     * @param code 左零右一
     * @param sb 用于拼接路径
     */
    public static void huffmanCodeTable(Node node,String code,StringBuilder sb){
        StringBuilder stringBuilder = new StringBuilder(sb);
        stringBuilder.append(code);
        if (node != null) {// node为空不作处理
            if(node.data == null){// 非叶子节点
                // 左递归
                huffmanCodeTable(node.left,"0",stringBuilder);
                // 右递归
                huffmanCodeTable(node.right,"1",stringBuilder);
            }else{
                // 找到了,直接添加
                map.put(node.data,stringBuilder.toString());
            }
        }
    }


    public static void preSort(Node node){
        if(node == null){
            System.out.println("二叉树为空");
        }else{
            node.preSort();
        }
    }

}

class Node implements Comparable<Node>{
    Byte data; // 存放数据本身
    int wright; // 存放节点权值,表示字符出现的次数
    Node left; // 指向左子节点
    Node right; // 指向右子节点
    public Node(Byte data,int wright){
        this.data = data;
        this.wright = wright;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + data +
                ", wright=" + wright +
                '}';
    }

    @Override
    public int compareTo(Node node) {
        // 按照从小到大的顺序进行排序
        return this.wright - node.wright;
    }

    // 前序遍历
    public void preSort(){
        System.out.println(this);
        if(this.left != null){
            this.left.preSort();
        }

        if(this.right != null){
            this.right.preSort();
        }
    }
}